1. Technical Field of the Invention
This invention relates generally to data storage systems, and more particularly to a storage system in which prefetching decisions are made by the storage device, taking advantage of information which the storage device has but which the host is unlikely to have, such as rotational position or what data are already cached by the storage device.
2. Background Art
Prefetching can improve system performance, by making data available earlier or faster than would be the case without prefetching. The greater the differences between the rates at which data can be read from a mass storage device such as a hard disk, and the rates at which that data can then be transferred to the processing system, the greater the benefit from prefetching. The more intelligently the prefetching is performed, the more benefit it will offer.
FIG. 1 illustrates a data processing system 10 such as is typical in the prior art. The system includes a processor 12 for performing logic operations of the system, a memory controller 14 for interfacing the processor to a memory 16 such as one or more subsystems of dynamic random access memory (DRAM), static random access memory (SRAM), read only memory (ROM), programmable read only memory (PROM), flash memory, and the like. The system further includes a host disk controller 18 for interfacing to a storage system 20 such as one or more of a hard disk drive (HDD), compact disc read only memory (CD-ROM), floppy disk drive, digital video disc (DVD), or the like, or even non-rotating storage such as a tape drive or a solid state bulk storage system.
The memory typically includes an application program 22 which performs operations desired by a user. The application runs on an operating system (OS) 24 which provides a higher-level abstraction and collection of routines for performing operations of the system, such as requests to open a file on the storage system. The memory typically also includes one or more drivers customized for operating various hardware systems of the data processing system, including a host storage driver 26 for the particular storage system.
When the application wants to, for example, read a portion of a file from the storage system, the application allocates an application buffer 28 which is an area of memory in which the requested data are to be stored. After allocating the application buffer, the application issues an OS call identifying the requested data and indicating the address of the application buffer to which the data are to be retrieved. If the OS has previously cached the requested data in an OS cache 30, such as a file system cache, the OS will simply copy the data from the OS cache to the application buffer and tells the application that the data retrieval has succeeded. If the requested data are not in the OS cache, the OS issues a call to the host storage driver. The driver may maintain a driver cache 32 and, if the requested data are found in the driver cache, the driver copies the requested data directly from the driver cache into the application buffer.
The storage system includes a storage drive 36 which may be any suitable mechanism such as one or more rotating hard disk platters, CD-ROM platters, DVD platters, and so forth, and/or one or more non-rotating mechanisms such as tape drives, solid state memory devices, and the like. The storage drive may include one or more data read devices such as a hard disk head mechanism (generally shown as “H”). The storage system includes one or more controllers such as a spin/seek controller 38 for controlling the various storage drives.
The storage system also includes a microcontroller 40 for performing logic operations of the storage system, and a storage controller memory 42 for holding data used in those logic operations. The storage controller memory may include registers 44 for passing parameters to or from the driver, and a storage buffer 46 through which requested data are delivered. The storage system may include a variety of prefetch algorithms 48 which the microcontroller executes in attempting to improve overall system performance by intelligently guessing which data are likely to be requested in the near future. The microcontroller can store prefetched data in a storage cache 50. Then, if that data is subsequently requested by the driver, the data can be transferred at the interface rate of the host disk controller, rather than at the typically much slower transfer rate of the storage drive, and without waiting for the head to seek to the correct cylinder and the platter to rotate to the correct sector.
Data actually requested may be termed “demand data”, and speculatively prefetched data may be termed “prefetch data”.
FIGS. 1 and 2 illustrate operation of the storage system. The seek/spin controller moves the head to the correct cylinder of the platter. At some time during the next full rotation of the platter, the requested block will pass beneath the head and be read into the storage buffer.
Unfortunately, existing prefetch schemes are either completely host driven or completely device driven, with no coordination between the host and the device. The host storage driver or the OS determines that some particular data, such as block 63 are likely to be needed next, and issues a “prefetch request”. If, while the storage system is servicing this prefetch request and is, for example, waiting for the disk to rotate to the correct track, the host issues a demand request for a different block, the demand request will be stalled until the prefetch request has been completed. This is especially problematic in systems in which the storage accesses are largely non-sequential, such as Windows desktop workloads.
Another problem can arise in prefetching schemes which automatically expand the scope of demand data requests to include prefetch data. These prefetch data are typically data which are previous and/or subsequent blocks contiguous to the demand blocks. If the host gets lucky, there is no problem. Often, however, the previous (prefetch) blocks may have started rotating past the head moments before the head was in position to read them; for example in FIG. 2 if the demand request block is block 62 and the driver decides to also fetch blocks 61 and 63 as prefetch data. The result is that the device disk controller will have to wait nearly a complete revolution of the platter before it can begin reading the data, which begins with block 61 that has just passed the head, even though the demand request block 62 itself has not yet begun passing the head. In this instance, the prefetch is very negatively efficient.
Yet another problem can arise when the host storage driver has asked for a prefetch block which is logically mapped to a physical block (such as block 64) which is “bad” and which has been remapped by the storage system to a different location (such as block 65) that is unknown to the host. Any requests to such blocks are likely to cause delays, because they are likely to mean moving the head to a different track, perhaps one far removed from the track of the demand request block.
Still another problem can arise when the host storage driver asks for prefetch data that go beyond the end of the current track and causes the request to cross a cylinder boundary. This causes a head seek and results in a negatively efficient prefetch.
In any of these situations, if the host storage driver had known more information about the state of the storage system, such as which track and sector the head were at, or which data were already in the storage cache, it might not have issued the prefetch request, or may have modified it, or may have delayed it.